package 动态规划.backageQuestion;

/**
 * 最长公共子序列问题
 *它寻找两个序列共有的最长子序列的长度，不要求子序列元素在原序列中连续。
 *
 * 思路分析：
 * 1：定义一个二维数组，dp[i][j]表示text1[0...i]和text2[0...j]的最长公共子序列的长
 * 2：状态转移方程：
 *   如果text1[i] == text2[j]，那么dp[i][j] = dp[i-1][j-1] + 1
 *   如果text1[i] != text2[j]，那么dp[i][j] = max(dp[i-1][j], dp[i][j-1])   text1的前i个字符和text2的前j个字符最大值是当前字符
 *
 * X[i-1] == Y[j-1]，则这两个字符一定在LCS中。此时，dp[i][j] = dp[i-1][j-1] + 1。
 * 如果当前字符不匹配，即 X[i-1] != Y[j-1]，则LCS可能是 X[0...i-2] 和 Y[0...j-1] 的LCS，或者是 X[0...i-1] 和 Y[0...j-2] 的LCS。
 *
 * 我们取这两种情况的较大者，因此 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
 * 3：初始化：dp 数组的所有元素初始化为 0。由于 dp[i][0] 和 dp[0][j] 代表的是任何字符串与空字符串的最长公共子序列，所以它们自然都是 0。
 * 4：填表： 按照行（或列）的顺序填充 dp 表。
 * 5：结果，dp[m][n];
 * @Author lf
 * @Date 3/19/2024
 */
public class LCS {
    public static int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length();
        int m = text2.length();

        int[][] dp =new int[n+1][m+1];

        for (int i = 1; i <= n ; i++) {
            for (int j = 1; j <= m ; j++) {
                if(text1.charAt(i-1) == text2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else {
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[n][m];
    }

    public static void main(String[] args) {
        String text1 = "ABCBDAB";
        String text2 = "BDCAB";
        System.out.println("The length of the LCS is: " + longestCommonSubsequence(text1, text2));
    }
}
